package bfs;

import java.util.LinkedList;
import java.util.List;

public class Template {

    List<LinkedList<Integer>> graph = new LinkedList<>();
    /**
     * 从s开始bfs遍历图的所有节点，且记录遍历的步数
     * 当走到目标节点target时，返回步数
     * @param s
     * @param target
     * @return
     */
    public int bfs(int s, int target) {
        boolean[] visited = new boolean[graph.size()];
        LinkedList<Integer> q = new LinkedList<>();
        q.offer(s);
        visited[s] = true;
        // 记录从 s 开始走到当前节点的步数
        int step = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int cur = q.poll();
                System.out.println("visit" + cur + "at step" + step);
                // 判断是否到达终点
                if (cur == target) {
                    return step;
                }
                // 将邻居节点放入队列，向四周扩散搜索
                for (int to : neighborsOf(cur)) {
                    if (!visited[to]) {
                        q.offer(to);
                        visited[to] = true;
                    }
                }
            }
            step++;
        }
        // 如果走到这里，说明图中没有找到目标节点
        return -1;
    }

    private int[] neighborsOf(int cur) {

    }
}
